package leetcode_位运算;

/**
 * 或值至少为 K 的最短子数组 II
 * 算法：位运算 + 滑动窗口
 *
 * @author yezh
 * @date 2025/1/16 15:06
 */
public class _3097 {

    public int minimumSubarrayLength(int[] nums, int k) {
        // 时间复杂度: O(nlogU), U: 数组中的最大数
        int ans = Integer.MAX_VALUE, n = nums.length;
        for (int i = 0; i < n; i++) {
            if (nums[i] >= k) return 1;
            // 当 nums[i] 是 nums[j] 的子集时, 结束循环
            for (int j = i - 1; j >= 0 && (nums[j] | nums[i]) != nums[j]; j--) {
                // nums[j]: nums[j] | nums[j + 1] | ... | nums[i]
                nums[j] |= nums[i];
                if (nums[j] >= k) ans = Math.min(ans, i - j + 1);
            }
        }
        return ans == Integer.MAX_VALUE ? -1 : ans;
    }

}
